//1.递归
class Solution {
public:
    int ans;   // 链表总长度
    int cur;   // 已处理节点数

    // 反转 head 开始的 k 个节点，返回新的子链表头
    ListNode* _my_sort(ListNode* head, int k) {
        ListNode* curr = head;
        ListNode* prev = nullptr;
        for (int i = 0; i < k; ++i) {
            ListNode* nxt = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nxt;
        }
        return prev;
    }

    ListNode* fanzhuan(ListNode* head, int k) {
        // 剩余不足 k，直接返回
        if (ans - cur < k) 
            return head;

        // 找到本段第 k 个节点 end
        ListNode* end = head;
        for (int i = 1; i < k; ++i) 
            end = end->next;

        // **先**保存下一组的头
        ListNode* next_head = end->next;

        // 反转本段，ret 为新头
        ListNode* ret = _my_sort(head, k);
        cur += k;  // 更新已处理计数

        // 接回并递归处理剩余
        head->next = fanzhuan(next_head, k);
        return ret;
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        // 统计总长度
        ans = 0; 
        cur = 0; 
        for (ListNode* p = head; p; p = p->next) 
            ++ans;
        return fanzhuan(head, k);
    }
};

//2.迭代版本，不用递归栈
class Solution {
public:
    // 反转 [start, end] 这段链表，返回 {newHead, newTail}
    pair<ListNode*, ListNode*> myReverse(ListNode* start, ListNode* end) {
        ListNode* prev = end->next;   // 反转后 start->next 要指向这里
        ListNode* curr = start;
        // 一直反到 end 节点后面
        while (prev != end) {
            ListNode* nxt = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nxt;
        }
        // 现在 prev 指向 end，curr 指向 end->next
        // 原 start 变成 newTail，end 变成 newHead
        return {end, start};
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        // 0) 哨兵节点，简化头部处理
        ListNode dummy(0);
        dummy.next = head;
        ListNode* prev = &dummy;  

        while (true) {
            // 1) 确认剩下是否还有 k 个节点
            ListNode* groupEnd = prev;
            for (int count = 0; count < k; ++count) {
                groupEnd = groupEnd->next;
                if (!groupEnd) {
                    // 不足 k 个，直接返回结果
                    return dummy.next;
                }
            }

            // 2) 标记本组和下组的边界
            ListNode* groupStart = prev->next;      // 本组第 1 个节点
            ListNode* nextGroup = groupEnd->next;   // 下组第 1 个节点

            // 3) 反转本组 [groupStart, groupEnd]
            auto result = myReverse(groupStart, groupEnd);
            ListNode* newHead = result.first;
            ListNode* newTail = result.second;

            // 4) 拼回主链表
            prev->next      = newHead;
            newTail->next   = nextGroup;

            // 5) 推进到下一组的前驱位置
            prev = newTail;
        }

        
        return dummy.next;
    }
};

